// https://www.lintcode.com/problem/merge-two-sorted-lists/description?_from=ladder&&fromId=6

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param l1: ListNode l1 is the head of the linked list
     * @param l2: ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    ListNode * mergeTwoLists(ListNode * l1, ListNode * l2) {
        ListNode * h1 = l1;
        ListNode * h2 = l2;
        ListNode * result = new ListNode(-1);
        ListNode * dummy = result;
        while (h1 && h2)
        {
            if (h1->val < h2->val) 
            { 
                result->next = h1;
                h1 = h1->next;
            }
            else 
            {
                result->next = h2;
                h2 = h2->next;
            }
            result = result->next;
        }
        if (h1) result->next = h1;
        else if (h2) result->next = h2;
        return dummy->next;
    }
};